package LeetcodeTest_five;
//递增顺序查找树

import java.util.ArrayList;
import java.util.Scanner;

public class increasingBST
{
    public static void main(String[] args)
    {
        TreeNode T=new TreeNode(0);
        TreeNode r=new TreeNode(0);
        T=Solution.createTree(T);
        r=Solution.increasingBST(T);
        Solution.PrintNode(r);
    }
}
class Solution
{
    public static TreeNode increasingBST(TreeNode root)
    {
        ArrayList<Integer> a=new ArrayList<Integer>();
        PrintNode2(a,root);
        TreeNode r=new TreeNode(0);
        r=createTree2(a,0,r);
        return r;
    }
    //先序构建二叉树
    public static TreeNode createTree(TreeNode T)
    {
        Scanner reader=new Scanner(System.in);
        int a=reader.nextInt();
        TreeNode p=null;
        if (a==-1)
            p=null;
        else
            p = new TreeNode(a);
        T=p;
        if(T==null)
            return T;
        else
        {
            T.left = createTree(T.left);
            T.right = createTree(T.right);
        }
        return T;
    }
    //先序构建二叉树
    public static TreeNode createTree2(ArrayList<Integer> a,int i,TreeNode root)
    {
        TreeNode p =null;
        if(i<a.size()&&a.get(i)>=0 )
            p=new TreeNode(a.get(i));
        else
            p=null;
        root = p;
        if(root==null)
            return root;
        else
        {
            root.left=null;
            root.right = createTree2(a, i + 1, root.right);
        }
        return root;
    }
    //先序遍历二叉树
    public static void PrintNode(TreeNode T)
    {

        if(T!=null)
        {
            System.out.println(T.val);
            if(T.right!=null)
            {
                PrintNode(T.left);
                PrintNode(T.right);
            }
        }
        else
            System.out.println("null");
    }
    //中序遍历将节点值存入数组
    public static void PrintNode2(ArrayList a,TreeNode T)
    {
        if(T!=null)
        {
            PrintNode2(a,T.left);
            a.add(T.val);
            PrintNode2(a,T.right);
        }
    }
}
class TreeNode
{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
